package array;

/**
 * 实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列（即，组合出下一个更大的整数）。
 *
 * 如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
 *
 * 必须 原地 修改，只允许使用额外常数空间。
 *
 */
public class leetCode31_nextPermutation {

    public static void main(String[] args) {
        int[] nums = {1,5,1};
        nextPermutation(nums);
    }

    public static void nextPermutation(int[] nums){
        if(nums == null || nums.length < 2) return;

        int k = nums.length - 1;
        while (k - 1 >= 0 && nums[k - 1] >= nums[k]) {
            k--;
        }
        if(k == 0){
            reverse(nums,0,nums.length - 1);
        }else{
            int u = k;
            while (u + 1 <= nums.length - 1 && nums[k - 1] <= nums[u + 1]){
                u++;
            }
            // 找到交换点
            int tmp = nums[u];
            nums[u] = nums[k - 1];
            nums[k - 1] = tmp;

            reverse(nums,k,nums.length - 1);
        }

    }

    public static void reverse(int[] nums,int left,int right){
        if(left >= right || nums.length < 2) return;
        while (left < right){
            int tmp = nums[left];
            nums[left] = nums[right];
            nums[right] = tmp;
            left++;
            right--;
        }

    }



}
